﻿#pragma once

//公共头文件
#include<iostream>
#include<unordered_map>
#include<vector>
#include<map>
#include<algorithm>

#include<atomic>
#include<thread>
#include<mutex>

#include<time.h>
#include<assert.h>
#include<cstdlib>

using std::cout;
using std::cin;

//头文件条件编译，自动识别平台定义
#ifdef _WIN32
#include<Windows.h>
#else
	//linux对应头文件
#endif

static const size_t MAX_BYTES = 256 * 1024;//进程缓存的最大字节数 256KB
static const size_t NFREELIST = 208;//进程缓存256KB大小的情况下，对齐后共有208个桶（哈希桶大小）
static const size_t NPAGES = 129;//pagecache哈希桶桶数 下标0桶位无页资源 （1，128）
static const size_t PAGE_SHIFT = 13;//1^13(表示一个标准页的大小）右移13位；用于计算所需的页数

//不同平台下页号的大小定义
//因为：1.若是32位下，页号的取值范围是：2^32/2^13==2^19;这一取值范围size_t类型可包含
//但64位下：2^64/2^13==2^51,则大大超出类型size_t的数值包含范围会造成数值溢出问题，所以必须使用长整型：unsigned long long
//1.在32位配置：_WIN32被定义，_WIN64无定义    2.在64位配置：_WIN32与_WIN64均被定义
#ifdef _WIN64
	typedef unsigned long long PAGE_ID;
#elif _WIN32
	typedef size_t PAGE_ID;
#else
	//linux环境下
#endif


//封装接口，将不同Windows与Linux的接口做条件编译封装（越过标准库，直接向操作系统申请）
inline static void* SystemAlloc(size_t kpage)//申请page页的8k大小空间
{
#ifdef _WIN32//如果是Windows则使用其接口
	void* ptr = VirtualAlloc(0, kpage * 8 * 1024, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else//否则Linux接口
	//Linux API:brk()、mmap()
#endif
	if (ptr == nullptr)//差错处理
	{
		throw std::bad_alloc();
	}
	return ptr;
}

//释放堆空间
inline static void SystemFree(void* ptr)
{
#ifdef _WIN32
	VirtualFree(ptr, 0, MEM_RELEASE);
#else
	// sbrk unmmap
#endif
}

//将内存块的前4/8个字节返回，可修可改
static void*& NextObj(void* obj)
{
	return *(void**)obj;
}

//此类是用于管理切分好的小对象内存块(哈希桶内的自由链表） thread cache层
class FreeList
{
public:
	//头插(单个)
	void Push(void* obj)
	{
		assert(obj);
		NextObj(obj) = _freeList;//前4/8字节存下一节点地址
		_freeList = obj;//头指针调整位置
		++_size;
	}

	//插入（多个）
	void PushRange(void* start, void* end, size_t n)
	{
		NextObj(end) = _freeList;
		_freeList = start;

		//bug2 插入了少于n个的小内存块节点
		//int i = 0;
		//void* cur = start;
		//while (cur)//统计n的长度
		//{
		//	cur = NextObj(cur);
		//	i++;
		//}
		//if (i != n)//如果该段连续节点数不等于n则进入
		//{
		//	cout << " error" << std::endl;
		//}

		_size += n;
	}

	//删除（多个）
	void PopRange(void*& start, void*& end, size_t n)
	{
		assert(n >= _size);
		start = _freeList;
		end = start;
		for (size_t i = 0; i < n - 1; i++)
		{
			end = NextObj(end);
		}
		_freeList = NextObj(end);
		NextObj(end) = nullptr;
		_size -= n;
	}

	//头删
	void* Pop()
	{
		assert(_freeList);//若自由链表为空，则不头删
		void* obj = _freeList;
		_freeList = NextObj(obj);
		--_size;
		return obj;
	}

	//判断自由链表内是否为空
	bool Empty()
	{
		return _freeList == nullptr;
	}

	//返回申请上限值
	size_t& MaxSize()
	{
		return _maxSize;
	}

	//获取内存块个数
	size_t Size()
	{
		return _size;
	}

private:
	void* _freeList = nullptr;//构造
	size_t _maxSize = 1;//当发生thread cache向中心缓存申请空间后，所进行申请空间的上限（作用：防止一次性申请了过多的空间）
	size_t _size = 0;//内存块个数
};


//计算对象大小与哈希桶映射关系规则的类
class SizeClass
{
public:
	// 最少使用8byte对其，因为需要存指针，所以若使用4byte则64位下无法存指针
	// 整体控制在最多10%左右的内碎片浪费							   区间桶数计算：
	// [1,128]                8byte对齐       freelist[0,16)		   128/8=16
	// [128+1,1024]           16byte对齐      freelist[16,72)		   1024-128/16=56
	// [1024+1,8*1024]        128byte对齐     freelist[72,128)		  
	// [8*1024+1,64*1024]     1024byte对齐    freelist[128,184)
	// [64*1024+1,256*1024]   8*1024byte对齐  freelist[184,208)
	// 对齐数 / 对象字节数 < %12

	//子函数（计算对象大小对齐后的大小）
	//核心算法: 1.(bytes / alignNum + 1) * alignNum（常规算法，二者功能相同）  2.如下
	static inline size_t _RoundUp(size_t bytes, size_t alignNum)//参数：1.对象字节数 2.对齐数
	{
		return ((bytes + alignNum - 1) & (~(alignNum - 1)));//返回的是对齐后的对象大小
	}

	//用于对象内存块分配
	//计算对象大小对齐后的大小(作用：通过对象的大小，按照对齐操作，使其分为适合存储的内存块大小，便于自由链表存储）
	static inline size_t RoundUp(size_t size)//参数为对象的大小，byte为单位
	{
		if (size <= 128)//128byte
		{
			return _RoundUp(size, 8);//8byte对齐数
		}
		else if (size <= 1024)//1K
		{
			return _RoundUp(size, 16);//16byte对齐数
		}
		else if (size <= (8 * 1024))//8K
		{
			return _RoundUp(size, 128);//128byte对齐数
		}
		else if (size <= (64 * 1024))//64K
		{
			return _RoundUp(size, 1024);//1K对齐数
		}
		else if (size <= (256 * 1024))//256K
		{
			return _RoundUp(size, (8 * 1024));//8K对齐数
		}
		else//大于256K
		{
			return _RoundUp(size, 1 << PAGE_SHIFT);//1*8*1024 使用8K对齐
		}
	}

	//（子函数）计算对应桶下标
	static inline size_t _Index(size_t bytes, size_t  align_shift)//参数align_shift是一个偏移位，表示1的具体偏移数，其实也就是对齐数
	{
		//本质：（bytes+(1的左移位）-1）>> 右移位 - 1 （bytes+对齐数-1/对齐数-1）
		return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
	}

	//计算对象在桶的对应下标（作用：通过对象大小与对齐数，计算出其在哈希桶中的下标位置）
	static inline size_t Index(size_t bytes)
	{
		assert(bytes <= MAX_BYTES);//不大于256KB大小
		static int group_array[4] = { 16, 56, 56, 56 };// 每个区间有多少个链
		if (bytes <= 128) {
			return _Index(bytes, 3);
		}
		else if (bytes <= 1024) {
			return _Index(bytes - 128, 4) + group_array[0];
			//_Index（去除上个被对齐后的范围，对齐数偏移量）+ 上一个范围的桶总数 == 绝对桶下标位
		}
		else if (bytes <= 8 * 1024) {
			return _Index(bytes - 1024, 7) + group_array[1] + group_array[0];
		}
		else if (bytes <= 64 * 1024) {
			return _Index(bytes - 8 * 1024, 10) + group_array[2] + group_array[1]
				+ group_array[0];
		}
		else if (bytes <= 256 * 1024) {
			return _Index(bytes - 64 * 1024, 13) + group_array[3] +
				group_array[2] + group_array[1] + group_array[0];
		}
		else {
			assert(false);
		}
		return -1;
	}

	//thread cache向中心缓存申请空间，中心缓存分配多少内存（计算批次）
	static size_t NumMoveSize(size_t size)
	{
		assert(size > 0);
		//【2，512】
		//（对象越小，一次分配越多）
		//（对象越大，一次分配越少）
		int num = MAX_BYTES / size;//线程缓冲区大小上限/对象大小
		if (num < 2)
			num = 2;
		if (num > 512)
			num = 512;
		return num;
	}

	//将对象大小 * 批次转换成pagecache的页数
	static size_t NumMovePage(size_t size)
	{
		size_t num = NumMoveSize(size);//中心内存需要分配出的内存的批次
		size_t npage = num * size;//（批次*对象大小==总字节数）
		npage >>= PAGE_SHIFT;//总字节数 >> 13 （相当于总字节数/8K）
		if (npage == 0)
			npage = 1;
		return npage;
	}

};

//CentralCache（第二层）管理多个连续的页级大块内存结构（Span）  
struct Span
{
	PAGE_ID _pageId = 0;//页号(span编号）
	size_t _n = 0;//页数（当前桶内span总数）(多少页)

	//双向链表结构管理Span页
	Span* _next = nullptr;
	Span* _prev = nullptr;

	size_t _objSize = 0;//记录当前span节点的大小
	size_t _useCount = 0;//用于做小块内存的计数，为0时表示没有被分割过，否则反之
	void* _freeList = nullptr;//每一个Span内的切分好的小块内存块链表

	bool _isUse = false;//span是否在被使用
};

//带头双向循环链表(Span的管理结构） central cache层
class SpanList
{
public:
	SpanList()
	{
		_head = new Span;//调用span的默认构造
		_head->_next = _head;
		_head->_prev = _head;
	}

	//获取桶的头节点(前开后闭）
	Span* Begin()
	{
		return _head->_next;
	}

	//获取桶的尾节点（前开后闭）
	Span* End()
	{
		return _head;
	}

	//判断spanlist是否为空
	bool Empty()
	{
		return _head->_next == _head;
	}

	//头插span
	void PushFront(Span* span)
	{
		Insert(Begin(), span);
	}

	//头删span节点
	Span* PopFront()
	{
		Span* front = _head->_next;//取到哨兵位节点之后的第一个span节点
		Erase(front);//将spanlist链表中的front节点删除
		return front;
	}

	//指定位插入Span
	void Insert(Span* pos, Span* newSpan)//在pos点前插入
	{
		assert(pos);
		assert(newSpan);

		Span* prev = pos->_prev;//记录pos的前一个Span页
		prev->_next = newSpan;
		newSpan->_prev = prev;
		newSpan->_next = pos;
		pos->_prev = newSpan;
	}

	//删除span
	void Erase(Span* pos)//删除指定pos点前的Span
	{
		assert(pos);
		assert(pos != _head);//bug1:哨兵位被谁删除了？ 原因在于错误的将非对应桶位的span节点返回，它可能为空的头节点

		Span* prev = pos->_prev;
		Span* next = pos->_next;

		prev->_next = next;
		next->_prev = prev;
	}

private:
	Span* _head;
public:
	std::mutex _mtx;//桶锁(线程安全）
};
